Lịch sử của thị trấn Naumburg bắt đầu vào đầu thế kỷ thứ 9 và 10. Do thiếu tài liệu viết tay nên chi tiết và ngày chính xác không được xác định. Tuy nhiên, có khả năng là Chỉ huy Ekkehard I của Meissen, người đàn ông quyền lực nhất trên biên giới phía đông của Đế quốc La Mã Thần thánh sáng lập.[3]

Ông cho dựng lên một nơi cư trú trên một tảng đá cao khoảng 25 mét (82 ft) phía trên bờ phải của sông Saale, gần với sông Unstrut. Vị trí của lâu đài này được gọi là neweburg sau này trở thành "Naumburg", được chọn vì vị trí thuận lợi của nó với giao lộ của rất nhiều đường thương mại được quản lý tốt trên biên giới phía đông lịch sử Đông Francia (Vương quốc Đức) với các vùng đất của Polavian Slavs đã được sáp nhập vào Saxon Eastern March.

Ekkehard đã bị sát hại vào năm 1002 tại Tu viện Pöhlde ở vùng đồi Harz, nhưng không thể được chôn cất tại Naumburg, vì cả lâu đài lẫn tu viện đều chưa hoàn thành. Chỉ có duy nhất con trai của ông là, Herman I và Eckard II là những người hậu duệ của ông chuyển đến Georgenkloster tại Naumburg. Con trai của Ekkehard đã thành lập một nhà thờ giáo xứ nhỏ ở phía tây của khu vực xung quanh lâu đài để dành riêng cho Đức Trinh Nữ Maria